/**
 * js实现大数相加
 * 问题：
 * js中要实现两个大数相加，如果转成number类型，就会损失精度，因为已经超出number类型的范围
 */

// 1、使用bigInt类型(但是会存在一定的兼容性问题，ie不兼容)
function largeNumAdd1(num1, num2){
    let sum = BigInt(num1) + BigInt(num2)
    sum = sum + ''
    return sum
}

//2、使用位运算思想（整数大树相加）
function largeNumAdd2(num1,num2){
    let arr1 = num1.split('').reverse()
    let arr2 = num2.split('').reverse()
    let arr3 = []
    let maxLen = arr1.length > arr2.length ? arr1.length : arr2.length
    let isAdd = false // 是否需要进位
    for(let i = 0; i < maxLen; i ++){
        arr3[i] = (arr1[i] || 0) * 1 + (arr2[i] || 0) * 1 + (isAdd ? 1 : 0)
        if(arr3[i] > 9){
            isAdd = true
            arr3[i] = arr3[i] % 10
        } else {
            isAdd = false
        }
    }
    if(isAdd) arr3[maxLen] = 1
    let str = arr3.reverse().join('')
    return str
}

//数组组成树
//使用递归

/** 从数组中过滤出虚假值 
 * 像0、undefined、null、false、" ", ' '可以很容易地通过以下方法省略
*/
const array1 = [3, 0, 6, 7, '', false];
array1.filter(Boolean) //输出 [3, 6, 7]

//数组转树形结构的两种方法
//1、递归（性能差）
const generateTree = (list, parentId = 0, { idName = 'id', parentName = 'parentId', childrenName = 'children' } = {}) => {
    if(!Array.isArray(list)){
        new Error('type only Array')
        return list
    }
    return list.reduce((pre,cur) => {
        //找到parentId的子节点之后，递归找子节点的下一级节点
        if(cur[parentName] === parentId){
            const children = generateTree(list,cur[idName])
            if(children.length){
                cur[childrenName] = children
            }
            return [...pre, cur]
        }
        return pre
    },[])
}

//2、非递归方式（性能好）
const generateTree2 = (list, rootId = 0, { idName = 'id', parentIdName = 'parentId', childrenName = 'children'} = {}) => {
    if(!Array.isArray(list)){
        new Error('type only Array')
        return list
    }
    const objMap = {} //暂存数组以id为key的映射关系
    const result = []

    for(let item of list){
        const id = item[idName]
        const parentId = item[parentIdName]
        //该元素有可能已经放入map中，（找不到该项的parentId时会先放入map）
        objMap[id] = !objMap[id] ? item : { ...item, ...objMap[id] }
        const treeItem = objMap[id] //找到映射关系第一项（注意这里是引用）
        if(parentId === rootId){
            //已经到根元素则将映射结果放进结果集
            result.push(treeItem)
        } else {
            //若父元素不存在，则初始化父元素
            if(!objMap[parentId]){
                objMap[parentId] = []
            }

            //若无该根元素则放入map中
            if(!objMap[parentId][childrenName]){
                objMap[parentId][childrenName] = []
            }

            objMap[parentId][childrenName].push(treeItem)
        }
    }

    return result
}

/**
 * js实现回文判断
 */

 // 整数转换为字符串 -> 数组 -> 数组反转 -> 字符串，然后进行比较
 const isPalindrome = (x) => {
    if(x < 0){
        return false
    } else if(x >= 0 && x <= 9){
        return false
    }
    let b = x.toString();
    let a = b.split('').reverse().join('')
    if(a === b){
        return true
    } else {
        return false
    }
 }


 const isPalindrome1 = (x) => {
     if(x < 0){
         return false
     } else if(x >= 0 && x <= 9){
         return true
     }

     let arr = x.toString().split('')
     let left = 0, right = arr.length - 1
     while(right > left){
         if(arr[left] !== arr[right]){
             return false
         }
         left++
         right--
     }
     return true

 }



